#!/usr/bin/env python
#coding:utf-8

'''
练习了：类定义、类的多种构造方式（普通，用类方法构造）、链表使用。（类对象赋值类似于C++的指针）
'''
import os
import math

class ListNode(object):
	# 标准构造函数
	def __init__(self, x):
		self.val = x
		self.next = None

	# 用方法作为构造函数，给调用者更多的选择
	@classmethod
	def constructor_array(cls, x):
		cls = ListNode(x[0])

		p = cls
		for i in range(1, len(x)):
			p.next = ListNode(x[i])
			p = p.next

		return cls

	# 用 静态函数声明，则没有self参数，可以通过类名调用，也可以通过类实例调用
	@staticmethod
	def __print__(p):
		if p == None:
			print "Empty List!"
			return

		while p != None:
			print p.val,'->',
			p = p.next
		print 'None'

class Solution(object):
	@staticmethod   # 使用staticmethon方法声明此函数，就不需要调用者在构造类实例就能调用了
	def two_numbers(list1, list2):
		if None == list1: return list2
		if None == list2: return list1

		carry = 0
		l1 = list1
		l2 = list2
		list_head = None
		list_tail = None
		while True:
			if l1 == None and l2 == None and carry == 0:
				return list_head

			sum = 0
			if l1 != None:
				sum += l1.val
				l1 = l1.next
			if l2 != None:
				sum += l2.val
				l2 = l2.next
			sum += carry

			if list_head == None:
				list_head = ListNode(sum%10)
				list_tail = list_head
			else:
				list_tail.next = ListNode(sum%10)
				list_tail = list_tail.next

			carry = sum / 10


	def two_numbers_positive(list1, list2):
		if None == list1: return list2
		if None == list2: return list1

		carry = 0
		l1 = list1
		l2 = list2
		list_head = None
		list_tail = None
		while True:
			if l1 == None and l2 == None and carry == 0:
				return list_head

			sum = 0
			if l1 != None:
				sum += l1.val
				l1 = l1.next
			if l2 != None:
				sum += l2.val
				l2 = l2.next

			if list_head == None:
				list_head = ListNode(sum0)
				list_tail = list_head
			else:
				list_tail.next = ListNode(sum%10)
				list_tail = list_tail.next

			carry = sum / 10


if __name__ == "__main__":

	list1 = ListNode(2)
	list1.next = ListNode(4)
	list1.next.next = ListNode(3)
	list2 = ListNode.constructor_array([5,6,7,1])

	rtn = Solution.two_numbers(list1, list2)
	ListNode.__print__(rtn)
	rtn.__print__(rtn)


'''
给出两个 非空 的链表用来表示两个非负的整数。其中，它们各自的位数是按照 逆序 的方式存储的，并且它们的每个节点只能存储 一位 数字。

如果，我们将这两个数相加起来，则会返回一个新的链表来表示它们的和。

您可以假设除了数字 0 之外，这两个数都不会以 0 开头。

示例：

输入：(2 -> 4 -> 3) + (5 -> 6 -> 4)
输出：7 -> 0 -> 8
原因：342 + 465 = 807
'''